package 代码题.排列组合题目;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 给定一个字符数组，求出所有的的组合数，不包括空字符。没有顺序要求
 * 举例：{a,b,c}要求输出{a,b,c,ab,ac,bc,abc}。
 */
public class Combination {

    /**
     * 思路：即从n个字符中找m个字符的组合就可以了。
     * 然后for循环，从1到数组长度len
     *
     * 递归过程如下：
     * 我们可以把n个字符分成两部分，第一个字符和其他所有字符。
     * 如果组合里包含第一个字符，则下一步在剩余的字符里选取m-1个字符；
     * 如果组合里不包含第一个字符，则下一步在剩余的n-1个字符里选取m个字符，从中可以看出又是个递归的过程。
     *
     * @param args
     */

    static Stack<Character> stack = new Stack<>();

    public static void main(String[] args) {
        char[] array=new char[]{'a','b','c'};
        helper(array);
        System.out.println(helperMath("abc"));
    }


    public static void helper(char[] array){
        for ( int i = 1 ; i <= array.length ; i ++ )
            combination(array,0,i);
    }

    private static void combination(char[] strArr, int begin, int num) {
        if (num == 0) {
            System.out.println(stack);
            return;
        }
        if (begin >= strArr.length) {
            return;
        } else {
            //把第一个字符放入组合中,在剩余的字符中选取num-1个字符
            stack.push(strArr[begin]);
            combination(strArr, begin + 1, num - 1);
            //组合里不包含第一个字符,则下一步在剩余的字符中选取num个字符
            stack.pop();
            combination(strArr, begin + 1, num);
        }
    }

    /**
     * 使用公式法：也就是哈夫曼编码:n个不痛的字符组成的全排列个数为2^n-1
     * 从a——abc一次编号为 001——111。1就代表该位置出现字符。
     * 例如：001->c,010->b,101->ac......，所以原题就是要求输出"001"-"111"这2^n-1个组合对应的字符串。
     */
    public static ArrayList<String> helperMath(String s){
        int len = s.length();
        ArrayList<String> list = new ArrayList<String>();

        int count = (int) (Math.pow(2, len));
        for(int i = 1; i < count; ++i){
            String temp = "";
            String str = Integer.toBinaryString(i);

            while(str.length() < len){
                str = "0" + str;
            }

            for(int j = 0; j < str.length(); ++j){
                if(str.charAt(j) == '1'){
                    temp += s.charAt(j);
                }
            }

            list.add(temp);
        }
        return list;
    }

}
